package leetcode;

import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-13 10:08
 **/
public class LeetCode31 {

    /*public static void nextPermutation(int[] nums) {
        if (nums.length == 1) {
            System.out.println(Arrays.toString(nums));
            return;
        }
        int n = nums.length - 1;
        int k = nums.length - 2;
        while (k >= 0 && nums[k] >= nums[k + 1]) {
            --k;
        }
        //如果k == -1就说明了此序列已经是字典序中最大的数，没有更大的了，就按题意，输出其升序的序列。
        if (k == -1) {
            Arrays.sort(nums);
            System.out.println(Arrays.toString(nums));
            return;
        }
        while (nums[n] <= nums[k]) {
            --n;
        }
        //练习下使用异或运算^交换两个整数的值
        nums[n] = nums[n] ^ nums[k];
        nums[k] = nums[k] ^ nums[n];
        nums[n] = nums[n] ^ nums[k];
        //最后需要将nums[k]所在的索引后面的所有值进行排序
        //该sort方法的range是左闭右开的,即[k+1,nums.length);
        Arrays.sort(nums, k + 1, nums.length);
        //输出下一个排列
        System.out.println(Arrays.toString(nums));

    }*/

    public static void nextPermutation(int[] nums) {
        if (nums.length == 1) {
            System.out.println(Arrays.toString(nums));
            return;
        }
        int n = nums.length - 1;
        int k = nums.length - 2;
        while (k >= 0 && nums[k] >= nums[k + 1]) {
            --k;
        }
        //如果k == -1就说明了此序列已经是字典序中最大的数，没有更大的了，就按题意，输出其升序的序列。
        if (k == -1) {
            reverse(nums, 0, nums.length - 1);
            System.out.println(Arrays.toString(nums));
            return;
        }
        while (nums[n] <= nums[k]) {
            --n;
        }
        //使用异或运算^交换两个整数的值
        swap(nums, n, k);
        //最后需要将nums[k]所在的索引后面的所有值进行排序
        //反转[k + 1, nums.length - 1]的元素
        reverse(nums, k + 1, nums.length - 1);
        //输出下一个排列
        System.out.println(Arrays.toString(nums));

    }

    //反转数组
    public static void reverse(int[] nums, int fromIndex, int toIndex) {
        if (fromIndex == toIndex) {
            return;
        }
        while (fromIndex < toIndex) {
            // 亦或^完成两个整型变量的值替换
            swap(nums, fromIndex, toIndex);
            fromIndex++;
            toIndex--;
        }
    }

    //亦或交换数组两个索引处的元素
    public static void swap(int[] nums, int indexA,int indexB) {
        nums[indexA] = nums[indexA] ^ nums[indexB];
        nums[indexB] = nums[indexA] ^ nums[indexB];
        nums[indexA] = nums[indexA] ^ nums[indexB];
    }


    public static void main(String[] args) {
        int[] nums = {1,1};
        nextPermutation(nums);
    }
}
